-- Copyright (c) 2010, bkil.hu
-- This program is free software and can be distributed under the terms of
-- the GNU General Public License v2,
-- see COPYING for detailed licensing terms.
-- created on 2010-06-07 18:47
-- elementwise processing, general version

import Data.Maybe(catMaybes, listToMaybe, mapMaybe)
import Data.List(transpose)

data KV key value = KV key value deriving Show

instance Eq k => Eq (KV k v) where
    (==) (KV k1 _) (KV k2 _) = k1==k2

instance Ord k => Ord (KV k v) where
    (<=) (KV k1 _) (KV k2 _) = k1<=k2

-- optional type specs

type OKVL key value = [KV key value]
type OKVLL k v = [OKVL k v]
type MKV k v = Maybe (KV k v)
type OMKVL k v = [MKV k v]
type OMKVLL k v = [OMKVL k v]

type KVP k v = OMKVL k v -> OMKVL k v
-- constraint: for ln -> lm, length ln==n, length lm=m

ep_n_m :: Ord k => KVP k v -> OKVLL k v -> OKVLL k v
ep_n_m f = map catMaybes . transpose . rows f [] where
    rows f acc xss =
        case mapMaybe listToMaybe xss of
            [] -> reverse acc
            nonempty -> rows f (f x:acc) xs where
                (x,xs) = unzip $ map choose xss
                choose (y:ys) | y==next = (Just y, ys)
                choose l = (Nothing, l)
                next = minimum nonempty

ep_2_1 g xs ys = zs where
    [zs] = ep_n_m f [xs, ys]
    f [x, y] = [g x y]

ep_update u v = ep_2_1 f u v where
    f x Nothing = x
    f _ y = y

main = print $ ep_update db patch where
 db    = [KV 1 9, KV 3 8, KV 4 7, KV 5 6, KV 7 5]
 patch = [KV 2 5, KV 4 4, KV 6 3]
